决策树算法

本文引用周志华教授的“西瓜书”（书名为《机器学习》，不过因为书中以西瓜分类的例子贯穿全书，读者常趣称其为“西瓜书”）中对决策树模型的讲解，来介绍机器算法中一类重要的算法——决策树的基本原理。

基本流程

决策树(decision tree) 是一类常见的机器学习方法. 以二分类任务为例, 我们希望从给定训练数据集学得一个模型用以对新示例进行分类, 这个把样本分类的任务, 可看作对 “当前样本属于正类吗?” 这个问题的 “决策” 或 “判定” 过程.

顾名思义, 决策树是基于树结构来进行决策的, 这恰是人类在面临决策问题时一种很自然的处理机制. 例如, 我们要对“这是好瓜吗?” 这样的问题进行决策时, 通常会进行一系列的判断或 “子决策” : 我们先看 “它是什么颜色?” , 如果是 “青绿色” , 则我们再看 “它的根蒂是什么形态?”, 如果是“蜷 缩”, 我们再判断 “它敲起来是什么声音?”, 最后, 我们得出最终决策: 这是个好瓜. 这个决策过程如图所示：

显然, 决策过程的最终结论对应了我们所希望的判定结果, 例如 “是” 或 “不是”好瓜; 决策过程中提出的每个判定问题都是对某个属性的 “测试”, 例如 “色泽=?” “根蒂=?” ; 每个测试的结果或是导出最终结论, 或是导出 进一步的判定问题, 其考虑范围是在上次决策结果的限定范围之内, 例如若在 “色泽 = 青绿” 之后再判断 “根蒂 = ?”, 则仅在考虑青绿色瓜的根蒂. 一般的, 一棵决策树包含一个根结点、若干个内部结点和若干个叶结点;

显然, 决策树的生成是一个递归过程. 在决策树基本算法中, 有三种情形会导致递归返回:

在第(2)种情形下, 我们把当前结点标记为叶结点, 并将其类别设定为该结点所含样本最多的类别; 在第(3)种情形下, 同样把当前结点标记为叶结点, 但 将其类别设定为其父结点所含样本最多的类别. 注意这两种情形的处理实质不同: 情形(2)是在利用当前结点的后验分布, 而情形(3)则是把父结点的样本分布作为当前结点的先验分布.

划分选择

由算法过程可看出, 决策树学习的关键是第 8 行, 即如何选择最优划分属性. 一般而言, 随着划分过程不断进行, 我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的 “纯度” (purity)越来越高.

信息增益

“信息熵” (information entropy)是度量样本集合纯度最常用的一种指标. 假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_{k}(k=1,2, \ldots,|\mathcal{Y}|)$, 则 $D$ 的信息熵定义为
$$ \operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log _{2} p_{k} $$ $\operatorname{Ent}(D)$ 的值越小, 则 $D$ 的纯度越高.

假定离散属性 $a$ 有 $V$ 个可能的取值 $\left\{a^{1}, a^{2}, \ldots, a^{V}\right\}$, 若使用 $a$ 来对样本集 $D$ 进行划分, 则会产生 $V$ 个分支结点, 其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^{v}$ 的样本, 记为 $D^{v}$. 我们可根据上式计算出 $D^{v}$ 的信息熵, 再考虑到不同的分支结点所包含的样本数不同, 给分支结点赋予权重 $\left|D^{v}\right| /|D|$, 即样本数越多的分支结点的影响越大, 于是可计算出用属性 $a$ 对样本集 $D$ 进行 划分所获得的 “信息增益” (information gain)

$$ \operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right) $$

一般而言, 信息增益越大, 则意味着使用属性 $a$ 来进行划分所获得的 “纯度提升” 越大. 因此, 我们可用信息增益来进行决策树的划分属性选择, 即在算法第 8 行选择属性 $a_{*}=\underset{a \in A}{\arg \max } \operatorname{Gain}(D, a)$. 著名的 ID3 决策树学习算 法 [Quinlan, 1986] 就是以信息增益为准则来选择划分属性.

以下表中的西瓜数据集为例, 该数据集包含 17 个训练样例, 用以学习一棵能预测没剖开的是不是好瓜的决策树. 显然, $|\mathcal{Y}|=2$. 在决策树学习开始时, 根结点包含 $D$ 中的所有样例, 其中正例占 $p_{1}=\frac{8}{17}$, 反例占 $p_{2}=\frac{9}{17}$. 于是, 可计算出根结点的信息熵为 $$ \operatorname{Ent}(D)=-\sum_{k=1}^{2} p_{k} \log _{2} p_{k}=-\left(\frac{8}{17} \log _{2} \frac{8}{17}+\frac{9}{17} \log _{2} \frac{9}{17}\right)=0.998 $$

然后, 我们要计算出当前属性集合 $\{色泽, 根蒂, 敲声, 纹理, 脐部, 触感\}$ 中每个属性的信息增益. 以属性 “色泽” 为例, 它有 3 个可能的取值: $\{$ 青绿, 乌 黑, 浅白}. 若使用该属性对 $D$ 进行划分, 则可得到 3 个子集, 分别记为: $D^{1}$ (色 泽 $=$ 青绿), $D^{2}$ (色泽 $=$ 乌黑), $D^{3}$ (色泽 $=$ 浅白). 子集 $D^{1}$ 包含编号为 $\{1,4,6,10,13,17\}$ 的 6 个样例, 其中正例占 $p_{1}=\frac{3}{6}$, 反例占 $p_{2}=\frac{3}{6} ; D^{2}$ 包含编号为 $\{2,3,7,8,9,15\}$ 的 6 个样例, 其中正、反例分 别占 $p_{1}=\frac{4}{6}, p_{2}=\frac{2}{6} ; D^{3}$ 包含编号为 $\{5,11,12,14,16\}$ 的 5 个样例, 其中正、 反例分别占 $p_{1}=\frac{1}{5}, p_{2}=\frac{4}{5}$. 根据信息熵公式可计算出用 “色泽” 划分之后所获得 的 3 个分支结点的信息熵为 $$ \begin{aligned} &\operatorname{Ent}\left(D^{1}\right)=-\left(\frac{3}{6} \log _{2} \frac{3}{6}+\frac{3}{6} \log _{2} \frac{3}{6}\right)=1.000 \\ &\operatorname{Ent}\left(D^{2}\right)=-\left(\frac{4}{6} \log _{2} \frac{4}{6}+\frac{2}{6} \log _{2} \frac{2}{6}\right)=0.918 \\ &\operatorname{Ent}\left(D^{3}\right)=-\left(\frac{1}{5} \log _{2} \frac{1}{5}+\frac{4}{5} \log _{2} \frac{4}{5}\right)=0.722 \end{aligned} $$ 于是, 根据式可计算出属性 “色泽” 的信息增益为

$$ \begin{aligned} \operatorname{Gain}(D, \text { 色泽 }) &=\operatorname{Ent}(D)-\sum_{v=1}^{3} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right) \\ &=0.998-\left(\frac{6}{17} \times 1.000+\frac{6}{17} \times 0.918+\frac{5}{17} \times 0.722\right) \\ &=0.109 . \end{aligned} $$

类似的, 我们可计算出其他属性的信息增益: $$ \begin{aligned} &\operatorname{Gain}(D, \text { 根蒂 })=0.143 ; \quad \operatorname{Gain}(D, \text { 敲声 })=0.141 ; \\ &\operatorname{Gain}(D, \text { 纹理 })=0.381 ; \operatorname{Gain}(D, \text { 脐部 })=0.289 ; \\ &\operatorname{Gain}(D, \text { 触感 })=0.006 . \end{aligned} $$ 显然, 属性 “纹理” 的信息增益最大, 于是它被选为划分属性. 下图给出了基于 “纹理” 对根结点进行划分的结果, 各分支结点所包含的样例子集显示在结点中

然后, 决策树学习算法将对每个分支结点做进一步划分. 以图中第一个分支结点( “纹理=清晰”) 为例, 该结点包含的样例集合 $D^{1}$ 中有编号为 $\{1$, $2,3,4,5,6,8,10,15\}$ 的 9 个样例, 可用属性集合为 $\{$ 色泽, 根蒂, 敲声, 脐部, 触感 $\}$. 基于 $D^{1}$ 计算出各属性的信息增益: $$ \begin{aligned} &\operatorname{Gain}\left(D^{1} \text {, 色泽 }\right)=0.043 ; \quad \operatorname{Gain}\left(D^{1}, \text { 根蒂 }\right)=0.458 ; \\ &\operatorname{Gain}\left(D^{1} \text {, 敲声 }\right)=0.331 ; \operatorname{Gain}\left(D^{1}, \text { 脐部 }\right)=0.458 ; \\ &\operatorname{Gain}\left(D^{1} \text {, 触感 }\right)=0.458 . \end{aligned} $$

“根蒂”、“脐部”、“触感” 3 个属性均取得了最大的信息增益, 可任 选其中之一作为划分属性. 类似的, 对每个分支结点进行上述操作, 最终得到的 决策树如图所示.

参考资料：